/*
 * Buddy alloc manager.
 *
 * Copyright (C) 2014 Ingenic Semiconductor Co.,Ltd
 * Author: Aeolus <weiqing.yan@ingenic.com>
 */

#include <stdint.h>
#include <string.h>
#include <stdio.h>

#include <imp/imp_log.h>

#include "buddy_alloc.h"
#ifdef DMALLOC
#include <imp/dmalloc.h>
#endif
#define TAG "Buddy Alloc"

#define ALREADY_INIT_CODE 0x5a5a5a5a
#define INIT_CODE_SIZE sizeof(ALREADY_INIT_CODE)

#define BUDDY_BLOCK_SIZE (2 << 12)

#define ALIGN_ADDR(base) (((base)+((BUDDY_BLOCK_SIZE)-1))&~((BUDDY_BLOCK_SIZE)-1))
#define ALIGN_SIZE(size) ((size)&~((BUDDY_BLOCK_SIZE)-1))

typedef struct {
	uint32_t base;
	int size;
} BuddyInfo;

typedef enum {
	TOKEN_HEAD,
	TOKEN_LEFT,
	TOKEN_RIGHT
} BlockToken;

struct BuddyBlockInfo;
typedef struct BuddyBlockInfo BuddyBlockInfo;
struct BuddyBlockInfo{
	BuddyBlockInfo *info_l; /* left */
	BuddyBlockInfo *info_r; /* right */
	int level;
	int level_num;
	BlockToken token;
	uint32_t addr;
	int size;
	int used;
};

static BuddyInfo g_buddy = {0};
static BuddyBlockInfo *head = NULL;
static uint32_t g_block_info_addr = 0;

static BuddyBlockInfo *buddy_get_info_offset(BuddyBlockInfo *info)
{
	return ((BuddyBlockInfo *)((uint32_t)(info) - g_buddy.base));
}

static BuddyBlockInfo *buddy_get_info_addr(BuddyBlockInfo *info)
{
	return ((BuddyBlockInfo *)((uint32_t)(info) + g_buddy.base));
}

static int buddy_add_list(BuddyBlockInfo *info)
{
	int ret = 0;
	info->info_l = (BuddyBlockInfo *)(g_block_info_addr + sizeof(BuddyBlockInfo));
	info->info_r = (BuddyBlockInfo *)(g_block_info_addr + 2 * sizeof(BuddyBlockInfo));
	g_block_info_addr += (2 * sizeof(BuddyBlockInfo));

	info->info_l->level = info->level + 1;
	info->info_l->level_num = info->addr / (info->size / 2);
	info->info_l->token = TOKEN_LEFT;
	info->info_l->addr = info->addr;
	info->info_l->size = info->size / 2;
	info->info_l->used = 0;

	info->info_r->level = info->level + 1;
	info->info_r->level_num = info->addr / (info->size / 2) + 1;
	info->info_r->token = TOKEN_RIGHT;
	info->info_r->addr = info->addr + info->size / 2;
	info->info_r->size = info->size / 2;
	info->info_r->used = 0;
/*
	IMP_LOG_DBG(TAG, "\ninfo->info_l->level = %d\n", info->info_l->level);
	IMP_LOG_DBG(TAG, "info->info_l->level_num = %d\n", info->info_l->level_num);
	IMP_LOG_DBG(TAG, "info->info_l->token = %d\n", info->info_l->token);
	IMP_LOG_DBG(TAG, "info->info_l->addr  = 0x%08x\n", info->info_l->addr );
	IMP_LOG_DBG(TAG, "info->info_l->size  = %d\n", info->info_l->size );
	IMP_LOG_DBG(TAG, "info->info_l->used  = %d\n", info->info_l->used );

	IMP_LOG_DBG(TAG, "\ninfo->info_r->level = %d\n", info->info_r->level);
	IMP_LOG_DBG(TAG, "info->info_r->level_num = %d\n", info->info_r->level_num);
	IMP_LOG_DBG(TAG, "info->info_r->token = %d\n", info->info_r->token);
	IMP_LOG_DBG(TAG, "info->info_r->addr  = 0x%08x\n", info->info_r->addr );
	IMP_LOG_DBG(TAG, "info->info_r->size  = %d\n", info->info_r->size );
	IMP_LOG_DBG(TAG, "info->info_r->used  = %d\n", info->info_r->used );
*/
	if((info->size / 2) <= BUDDY_BLOCK_SIZE) {
		info->info_l = buddy_get_info_offset(info->info_l);
		info->info_r = buddy_get_info_offset(info->info_r);
		return 0;
	}

	ret = buddy_add_list(info->info_l);
	if(ret != 0) {
		IMP_LOG_ERR(TAG, "buddy_add_list error\n");
		return ret;
	}

	ret = buddy_add_list(info->info_r);
	if(ret != 0) {
		IMP_LOG_ERR(TAG, "buddy_add_list error\n");
		return ret;
	}

	/*
	 * Struct point need to use address offset,
	 * cannot use an absolute address,
	 * otherwise the other process cannot shared.
	 */

	info->info_l = buddy_get_info_offset(info->info_l);
	info->info_r = buddy_get_info_offset(info->info_r);

	return 0;
}

static int buddy_check_child_block_is_used(BuddyBlockInfo *info)
{
	int ret = 0;

	if(info->used == 1)
		return info->used;

	if(info->info_l == NULL || info->info_r == NULL)
		return info->used;

	ret = buddy_check_child_block_is_used(buddy_get_info_addr(info->info_l));
	if(ret == 0)
		ret = buddy_check_child_block_is_used(buddy_get_info_addr(info->info_r));

	return ret;
}

static BuddyBlockInfo *buddy_request_block(BuddyBlockInfo *info, int size)
{
	BuddyBlockInfo *t_info = NULL;

	if(info->size >= (2 * size) && (info->used == 0)) {
		if(info->info_l == NULL || info->info_r == NULL) {
			info->used = 1;
			return info;
		}

		t_info = buddy_request_block(buddy_get_info_addr(info->info_l), size);
		if(t_info == NULL) {
			t_info = buddy_request_block(buddy_get_info_addr(info->info_r), size);
			if(t_info == NULL) {
				return NULL;
			}
		}
		t_info->used = 1;
		if(buddy_get_info_addr(info->info_l)->used == 1 && buddy_get_info_addr(info->info_r)->used == 1)
			info->used = 1;
		return t_info;
	}

	if((info->size >= size) && (info->used == 0)) {
		if(buddy_check_child_block_is_used(info)) {
			return NULL;
		}
		info->used = 1;
		return info;
	}

	return NULL;
}

static BuddyBlockInfo *buddy_release_block(BuddyBlockInfo *info, void *addr)
{
	BuddyBlockInfo *t_info = NULL;

	if(info->addr == (uint32_t)addr && (info->used == 1)) {
		info->used = 0;
		return info;
	}

	if(info->info_l && info->info_r) {
		t_info = buddy_release_block(buddy_get_info_addr(info->info_l), addr);
		if(t_info == NULL) {
			t_info = buddy_release_block(buddy_get_info_addr(info->info_r), addr);
			if(t_info == NULL) {
				return NULL;
			}
		}
		t_info->used = 0;
		if(buddy_get_info_addr(info->info_l)->used == 0 || buddy_get_info_addr(info->info_r)->used == 0)
			info->used = 0;
		return t_info;
	}

	return NULL;
}

static void buddy_dump_info(BuddyBlockInfo *info)
{
	IMP_LOG_INFO(TAG, "\ninfo->level = %d\n", info->level);
	IMP_LOG_INFO(TAG, "info->level_num = %d\n", info->level_num);
	IMP_LOG_INFO(TAG, "info->token = %d\n", info->token);
	IMP_LOG_INFO(TAG, "info->addr  = 0x%08x\n", info->addr + g_buddy.base);
	IMP_LOG_INFO(TAG, "info->size  = %d\n", info->size);
	IMP_LOG_INFO(TAG, "info->used  = %d\n", info->used);

	if(info->info_l && info->info_r) {
		buddy_dump_info(buddy_get_info_addr(info->info_l));
		buddy_dump_info(buddy_get_info_addr(info->info_r));
	}
}

static int buddy_init_list(void *base, int size)
{
	int ret = 0;
	if(head == NULL) {
		head = (BuddyBlockInfo *)(base + INIT_CODE_SIZE);
		head->level = 0;
		head->level_num = 0;
		head->token = TOKEN_HEAD;
		head->addr = 0;
		head->size = size;
		head->used = 0;
		g_block_info_addr = (uint32_t)(base + INIT_CODE_SIZE);
	}

	ret = buddy_add_list(head);
	if(ret != 0) {
		IMP_LOG_ERR(TAG, "buddy_add_list error\n");
		return ret;
	}
	return 0;
}

#if 0
static int buddy_check_init(void *base, int size)
{
	return (*(int *)(base));
}
#endif

static int buddy_set_init(void *base, int size)
{
	*(int *)(base) = ALREADY_INIT_CODE;
	return 0;
}

static int buddy_base_init(void *base, int size)
{
	int ret = 0;

	memset(base, 0, size);
	ret = buddy_init_list(base, size);
	if(ret != 0) {
		IMP_LOG_ERR(TAG, "buddy init list error\n");
		return ret;
	}

	return 0;
}

/* Buddy APIs */
/**
 * 0: success
 */
int buddy_init(void *base, int size)
{
	int ret = 0;
	uint32_t init_addr = (uint32_t)base;
	int init_size = size;
	if(base == NULL) {
		IMP_LOG_ERR(TAG, "Mem Manager mode init error, base addr is NULL\n");
		return -1;
	}

	if(size < BUDDY_BLOCK_SIZE) {
		IMP_LOG_ERR(TAG, "Mem Manager mode init error, buddy size is too small\n");
		return -1;
	}
/*
	init_addr = ALIGN_ADDR(init_addr);
	init_size = ALIGN_SIZE(init_size);
	if(ALREADY_INIT_CODE == buddy_check_init((void *)init_addr, init_size)) {
		head = (BuddyBlockInfo *)(init_addr + INIT_CODE_SIZE);
		g_buddy.base = init_addr;
		g_buddy.size = init_size;
		return 0;
	}

*/
	g_buddy.base = init_addr;
	g_buddy.size = init_size;

	ret = buddy_base_init((void *)init_addr, init_size);
	if(ret != 0) {
		IMP_LOG_ERR(TAG, "buddy base init error\n");
		return ret;
	}

	if(buddy_alloc(g_block_info_addr - g_buddy.base) == NULL) {
		IMP_LOG_ERR(TAG, "buddy alloc block info mem error\n");
		return -1;
	}

	if(buddy_set_init((void *)init_addr, init_size)) {
		IMP_LOG_ERR(TAG, "buddy set init value info error\n");
		return -1;
	}

	return 0;
}

void *buddy_alloc(int size)
{
	BuddyBlockInfo *t_info = NULL;

	if(head == NULL) {
		IMP_LOG_ERR(TAG, "buddy memery manager no inited\n");
		return NULL;
	}

	t_info = buddy_request_block(head, size);
	if(t_info == NULL) {
		IMP_LOG_ERR(TAG, "Can't alloc memery\n");
		return NULL;
	}

	IMP_LOG_DBG(TAG, "======= [%s] =========\n", __func__);
	IMP_LOG_DBG(TAG, "info->level = %d\n", t_info->level);
	IMP_LOG_DBG(TAG, "info->level_num = %d\n", t_info->level_num);
	IMP_LOG_DBG(TAG, "info->token = %d\n", t_info->token);
	IMP_LOG_DBG(TAG, "info->addr  = 0x%08x\n", t_info->addr + g_buddy.base);
	IMP_LOG_DBG(TAG, "info->size  = %d\n", t_info->size );
	IMP_LOG_DBG(TAG, "info->used  = %d\n", t_info->used );

	return (void *)(t_info->addr + g_buddy.base);
}

void buddy_free(void *ptr)
{
	BuddyBlockInfo *t_info = NULL;

	if(head == NULL) {
		IMP_LOG_ERR(TAG, "buddy memery manager no inited\n");
		return;
	}

	t_info = buddy_release_block(head, (void *)((uint32_t)ptr - g_buddy.base));
	if(t_info == NULL) {
		IMP_LOG_ERR(TAG, "Can't free memery\n");
		return;
	}

	IMP_LOG_DBG(TAG, "======= [%s] =========\n", __func__);
	IMP_LOG_DBG(TAG, "info->level = %d\n", t_info->level);
	IMP_LOG_DBG(TAG, "info->level_num = %d\n", t_info->level_num);
	IMP_LOG_DBG(TAG, "info->token = %d\n", t_info->token);
	IMP_LOG_DBG(TAG, "info->addr  = 0x%08x\n", t_info->addr + g_buddy.base);
	IMP_LOG_DBG(TAG, "info->size  = %d\n", t_info->size );
	IMP_LOG_DBG(TAG, "info->used  = %d\n", t_info->used );

	return;
}

void buddy_dump()
{
	if(head) {
		buddy_dump_info(head);
	}
}

